package Test;

import org.w3c.dom.Node;

import java.util.HashMap;
import java.util.Map;

public class LRU {
//    int capacity;
//    int size=0;
//    Node head=new Node();
//    Node tail=new Node();
//    class Node{
//        int key;
//        int val;
//        Node pre;
//        Node next;
//
//        public Node(){}
//        public Node(int key,int val){
//            this.key=key;
//            this.val=val;
//        }
//
//    }
//    public LRU(int capacity){
//            this.capacity=capacity;
//            head.next=tail;
//            tail.pre=head;
//    }
//    HashMap<Integer,Node> hashMap=new HashMap<>();
//    int get(int key){
//        Node node=hashMap.get(key);
//        if(node==null){
//            return -1;
//        }else {
//            makeRecently(node);
//            return node.val;
//        }
//    }
//    //注意：put方法中如果节点本身不存在则进行加入头部操作，makeRecently只操作于之前就存在于链表的节点
//    void put(int key,int val){
//        Node node=hashMap.get(key);
//        if(node==null){
//            node=new Node(key,val);
//            hashMap.put(key,node);
//            addToHead(node);
//            size++;
//            if(size>capacity){
//                Node last=removeLast();
//                hashMap.remove(last.val);
//                --size;
//            }
//        }else {
//            node.val=val;
//            hashMap.put(key,node);
//            makeRecently(node);
//        }
//    }
//
//    void makeRecently(Node node){
//        removeNode(node);
//        addToHead(node);
//    }
//
//    void addToHead(Node node){
//        node.pre=head;
//        node.next=head.next.next;
//        head.next.pre=node;
//        head.next=node;
//    }
//
//    void removeNode(Node node){
//        node.pre.next=node.next;
//        node.next.pre=node.pre;
//    }
//
//    Node removeLast(){
//        Node last=tail.pre;
//        removeNode(last);
//        return last;
//    }
}


/**
 * 在版本一中，我们自己利用HashMap和一个简单的双向链表来实现LRU缓存
 */
class LRUCache {

    // 双向链表节点定义
    class Node {
        int key;
        int val;
        Node prev;
        Node next;
        public Node(){};
        public Node(int key,int val){
            this.key=key;
            this.val=val;
        }
    }

    private int capacity;
    //保存链表的头节点和尾节点
    private Node first;
    private Node last;

    private Map<Integer, Node> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>(capacity);
    }

    public int get(int key) {
        Node node = map.get(key);
        //为空返回-1
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.val;
    }

    private void moveToHead(Node node) {
        /**********    删除节点     */
        if (node == first) {
            return;
        } else if (node == last) {
            last.prev.next = null;
            last = last.prev;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
/*************************************************/

        addToHead(node);
    }

    public void put(int key, int value) {
        Node node = map.get(key);

        if (node == null) {
            node = new Node(key,value);


            if(map.size() == capacity) {
                removeLast();
            }

            addToHead(node);
            map.put(key, node);
        } else {
            node.val = value;
            moveToHead(node);
        }
    }

    private void addToHead(Node node) {
        if (map.isEmpty()) {
            first = node;
            last = node;
        } else {
            node.next = first;
            first.prev = node;
            first = node;
        }
    }

    private void removeLast() {
        map.remove(last.key);
        Node prevNode = last.prev;
        if (prevNode != null) {
            prevNode.next = null;
            last = prevNode;
        }
    }

    @Override
    public String toString() {
        return map.keySet().toString();
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(3);
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(3, 3);
        cache.get(1);
        cache.put(4, 3);
        System.out.println(cache);
    }
}

